package com.currentbp.Interesting.likou.complete;

import com.currentbp.util.all.StringUtil;
import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024-04-24 17:20:10
 */
public class T215findKthLargest {
    /*
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
     */
    @Test
    public void t1() {
        System.out.println(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
        System.out.println(findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
    }

    public int findKthLargest(int[] nums, int k) {
        int[] newNums = sortedNums(nums);
        StringUtil.printObject(newNums);
        return newNums[k - 1];
    }

    private int[] sortedNums(int[] nums) {
        //做一个归并算法
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (end + start) / 2;
        mergeSort(nums, start, middle);
        mergeSort(nums, middle + 1, end);
        merge(nums, start, middle, middle + 1, end);
    }

    private void merge(int[] nums, int start1, int end1, int start2, int end2) {
        int[] tempResult = new int[end2 - start1 + 1];
        int index = 0;
        int index1 = start1;
        int index2 = start2;
        while (index1 <= end1 || index2 <= end2) {
            if (index1 > end1) {
                tempResult[index++] = nums[index2++];
                continue;
            }
            if (index2 > end2) {
                tempResult[index++] = nums[index1++];
                continue;
            }
            if (nums[index1] > nums[index2]) {
                tempResult[index++] = nums[index1++];
            } else {
                tempResult[index++] = nums[index2++];
            }
        }
        for (int i = start1, j = 0; i <= end2; i++, j++) {
            nums[i] = tempResult[j];
        }
    }
}
